COMMENT ⊗   VALID 00014 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{⊂CFJ≤G<NαGEOMETRIC MODELING THEORY.λ30I425,0P6JCFA}   SECTION 1.
C00005 00003	⊂1.1	Kinds of Geometric Models.⊃
C00007 00004		For a naive start,  first consider a  3-D array in which each
C00011 00005	
C00015 00006	
C00018 00007		
C00021 00008	
C00024 00009	
C00027 00010	{|λ10JA}
C00029 00011	⊂1.2	Polyhedron Definitions and Properties.⊃
C00033 00012
C00036 00013	⊂1.3	Camera, Light and Image Modeling.⊃
C00040 00014	⊂1.4	Related Modeling Work.⊃
C00044 ENDMK
C⊗;
{⊂C;FJ;≤G;<N;αGEOMETRIC MODELING THEORY.;λ30;I425,0;P6;JC;FA}   SECTION 1.
{JC;FD}                 GEOMETRIC MODELING THEORY.
{λ10;W250;JAFA}
	1.0	Introduction to Geometric Modeling.
	1.1	Kinds of Geometric Models.
	1.2	Polyhedron Definitions and Properties.
	1.3	Camera, Light and Image Modeling.
	1.4	Related Modeling Work.
{λ30;W0;I950,0;JUFA}
⊂1.0	Introduction to Geometric Modeling.⊃

	In  the specific  context of  computer  vision and  graphics,
<geometric modeling>  refers to constructing computer representations
of physical objects,   cameras,   images  and light for  the sake  of
simulating their  behavior. In Artificial Intelligence,   a geometric
model is  a kind of world model; ignoring subtleties, geometric world
modeling is distinguished from semantic and logical world modeling in
that  it is quantitative  and numerical  rather than  qualitative and
symbolic.  The  notion of a  world model requires  an external  world
environment to be modeled,  an internal  computer environment to hold
the  model,   and a  task performing  entity  to use  the model.   In
Geometry,  modeling is a synthetic problem,  like a construction with
ruler  and straight  edge, modeling  problems require  an algorithmic
solution rather than a proof.  The word <geometric> is an appropriate
adjective to this kind of modeling in that it is a combination of the
greek words  ≤gho≥ (world) and ≤metria≥ (measuring)  which is exactly
the activity to be automated. {Q}
⊂1.1	Kinds of Geometric Models.⊃

	The main  problem  of geometric  modeling is  to invent  good
methods for representing  arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid,   opaque,
and macroscopic with a  mathematically well behaved surface. Physical
objects  include: the earth, chairs, roads,   and plastic toy horses.
Such objects can  be moved about in  space with the restriction  that
two  objects can not  occupy the same  space at  the same time.   The
scope of the  modeling problem  can be appreciated  by examining  the
virtues and drawbacks of the models in box 1.1.
{|;λ10;JA}
BOX 1.1{JC}  TEN KINDS OF GEOMETRIC MODELS.
{↓}
Space Oriented:
	1. 3-D Space Array.
	2. Recursive Cells.
	3. 3-D Density Function.
	4. 2-D Surface Functions.
	5. Parametric Surface Functions.
{↑;W640;}
Object Oriented:
	6. Manifolds.
	7. Polyhedra.
	8. Volume Elements.
	9. Cross Sections.
 	10. Skeletons.
{|;λ30;JU}

	For a naive start,  first consider a  3-D array in which each
element indicates  the presence or absence of  solid matter in a cube
of space.  Such a 3-D  space array has the very desirable  properties
of <spatial addressing> and <spatial uniqueness> in their most direct
and  natural form. Spatial addressing refers  to finding out what the
model  contains  within a  distance  R  of  a  locus  X,Y,Z;  spatial
uniqueness refers to the property that physical solids can not occupy
the same space  simultaneously. A first drawback of the space
array idea is illustrated by the apparently legal FORTRAN statement:
{≤J;JC} DIMENSION SPACE(100000,100000,100000)
\The problem with such  a dimension statement is that  no present day
computer  memory is large  enough to  contain a 10≤15≥ element array.
Smaller space  arrays can  be useful  but necessarily  can not  model
large  volumes with  high resolution.   A  further drawback  of space
arrays  is that  objects and surfaces  are not  readily accessible as
entities; that  is  a space  array lacks  the  desirable property  of
<object  coherence>. Coherence is  the <sine  qua non> of  an object;
physical objects  tend to  hang together,  to be  self connected,  in
short to be coherent.{≤G}

	The space array  idea can be  salvaged by grouping  blocks of
elements  with  the  same value  together,    the addressing  process
becomes more complicated but  the overall memory required is  reduced
and the  two desired properties can  be maintained. One way  of doing
this   (which  has  been  discovered   in  several  applications)  is
<recursive cells>; the whole space is considered to be a cell; if the
space is not homogeneous then  the first cell is divided into two (or
four or eight) sub  cells and the criterion  is applied again.   This
technique allows  the  spatial sorting  of objects  when the  object
models can be  subdivided  at  each  recursion without  losing  their
properties as objects.

	Another salvageable  naive  modeling idea  is that  arbitrary
objects  can  be  expressed  as  algebraic  functions.   In  physics,
physical objects  are  frequently referred  to as  three  dimensional
density functions W=≤r≥(X,Y,Z).  Unfortunately such density functions
can  not be  written  out for  objects such  as a  typing chair  or a
plastic horse  without  resorting to  a  programming language  or  an
extensive  table (which  is  equivalent to  the  space array  model).
Objects that are  essentially 2-D  can be approximated  by a  surface
function Z  = F(X,Y).  For example  landscape may  be represented  by
geodetic maps in such a 2-D fashion.

	By definition,  a function is single valued; consequently the
description of even modestly complicated objects can not be expressed
directly  as  a  single  function  of  orthogonal  rectilinear  space
coordinates X,   Y and Z.  It is necessary either to adopt parametric
functions or  to  subdivide  the object  into  portions that  can  be
described  by simple functions  of Cartesian  variables.   The former
course involves establishing a  system of surface coordinates  (U,V),
latitudes and longitudes,  on the object  in which functions  for the
X,Y,Z locus  of the object's surface are  expressed. The advantage of
parametric functions is that extended arbitrary curve surfaces can be
expressed; some of  the disadvantages are that  parametric curves may
be self intersecting,  they are not easy to modified locally, and the
functions become impractical  before the shapes of  mundane artifacts
can be achieved. Consequently parametric representations are combined
with object subdivision  into portions,  which is  the latter  course
called <segmentation>.  The process of  usefully segmenting an object
without  destroying its  coherence is a  major problem  requiring the
combination of spatial,  functional and objective representations.

	In  passing from  space oriented  models  to object  oriented
models,  observe  that the same dichotomy appears at the frontiers of
physics where on the one hand the quantum field particle  wave theory
of objects  has yet  to be reconciled  with the  general relativistic
theory  of the space  that contains  the objects. Also  in passing, I
wish to note that sophisticated representations of time is beyond the
scope of this discussion,  although an advanced problem solving robot
will want to run world simulations along multiple time paths.

	After existence in space  and time, another general  property
of physical objects is  that they can be enclosed by  an unbroken two
dimensional  surface  with an  unabiguous inside  and  outside; which
touchs upon the mathematical topic (celebrated in song by Tom Lehrer)
of  the  algebraic  topology  of  locally  Euclidean  transitions  of
infinitely  differentiable oriented Riemann  manifolds.  A <manifold>
is the mathematical  abstraction of a  surface; a <Riemann>  manifold
has  a metric  function;  an <oriented>  manifold  has a  unambiguous
inside and an outside; the phrase <infinitely differentiable> can  be
taken to  mean that  the surface  is smooth  and continuous; and  the
phrase  <locally  Euclidean  transitions> refers  to  the  process of
segmenting the  object  into portions  that  can be  approximated  by
relatively  simple  functions.    In particular,    the  2-D  Riemann
submanifold  embedded  in  3-D Euclidean  space  is  the mathematical
object that comes closest to representing the shape and extent of the
surface  of  a  physical  object;  such  manifolds  are  conveniently
approached  through  the  topology  of  surfaces  which  in  turn  is
computationally approached by means of polyhedra.

	
	The topology of a  2-D Riemann submanifold embedded in  a 3-D
Euclidean space is  composed of three kinds of simplex: the 0-Simplex
(or  vertex), the  1-Simplex  (or  edge),    and  the  2-Simplex  (or
triangle). In  topological analysis  2-D Riemann submanifolds  may be
divided  into faces,   edges and vertices such  that Eulers equations
F-E+V=2-2*H is satisfied (where F  is the number of faces,  E  is the
number of edges,   V is the number of vertices and  H is the genus or
number of handles of the manifold); and such that the surface of  the
manifold can be approximated by local functions  over each face which
are Euclidean  and which fit together smoothly at  all the edges.  By
introducing  a  sufficient  (but  finite)  number  of  triangles  the
manifold  can  be  approximated  to within  an  epsilon  by  constant
functions, yielding the geometric object called the <polyhedron>.

	The  main inherent  advantage  of a  polyhedral model  is its
coherent surface  topology of  faces,  edges  and vertices.   Such  a
surface  can  be  subdivided  without  losing its  coherence  or  the
coherence of the object.  The disadvantages of polyhedra include  the
lack of spatial uniqueness and  spatial addressing which necessitates
computation to be  done to detect and prevent spatial conflict and to
find the portions  of an entity  occupying a  given volume.   Another
feature of polyhedra  (which can be an advantage  or disadvantage) is
that all the (<Gaussian>) curvature happens suddenly at the vertices;
however by  associating higher ordered  approximation functions  with
each face the model of  a continous 2-D manifold can be made which is
a  more  conventional  curved  object  representation.  Nevertheless,
polyhedra are intrinsically a general curved object representation.

	Returning  to  the  survey, arbitrary  objects  can  also  be
described  by listing a set  of cross sections taken  at a sufficient
number of cutting planes; this is  how the shape of a ship's hull  or
an airplane's wing is specified.  Cross sections have the interesting
feature  of good  space modeling  on one  axis.   Forsaking arbitrary
shaped objects,  large classes of things can be described in terms of
a small  set of basic volume  elements.  For  example, [Roberts]* and
others have built  models of familar  objects using only  rectangular
and triangular right prisms. Although,  arbitrary solid polyhedra can
be  constructed out of  tetrahedrons (the  3-simplex); no significant
general modeling  system exists  using this  potentially  interesting
approach.

	Skeletal models  are based  on abstracting  an object  into a
stick  figure and by associating a diameter  or set of cross sections
with the sticks. In particular,  spine cross section models have been
pursued  at Stanford by  [Agin] and  [Nervatia]. Spine  cross section
models have the advantage of being able to express many objects in  a
concise form suitable  for recognition,  however spine  cross section
models can not be used directly for arbitrary shapes. Finally,  it is
often useful to represent  physical objects by weak geometric  models
such as  by a  sets of  spheres or sets  of incoherent  surface point
(that is  unconnected).  It is interesting to note that the <reality>
that the robot in  Winograd's thesis [Winograd 71] could  talk about,
was  a blocks world  based on  a geometric  model consisting  only of
points,   size  of block,    and a  two  page LISP  subroutine  named
FINDSPACE.{H4;I∂0,0;V∂0,1260;I∂30,0;
}* All square bracketed symbols are references listed in section 11.1

	Beyond the particular kinds of geometric models, four general
purpose  modeling techniques  deserve special mention  and isolation:
prototype instance  structure,   parts  tree structure,    resolution
limited structure,  and procedure generated structure. Superficially,
the  prototype instance  structure is  a memory  efficiency technique
based on storing generalizations  (prototypes) which can be  bound to
specific  cases (instances) as  the occassion  demands.   Parts' tree
structure is a  memory management technique  of organizing the  whole
universe of  discourse as a  tree data  structure, where objects  are
composed  of  sub  objects.    Resolution  limited  structure  is  an
excellent memory accessing technique, where depending on  a specified
scale of interest  different models are retrieved  or even generated.
Finally, procedure generated structure concerns the trade-off between
storing and recomputing a model; namely recomputing the  details of a
model as they  are needed is a good  idea for extending computational
resources. Now the  danger to be  avoided is to  mistake the  general
modeling techniques for the geometric model itself.  Given a modeling
regime   it   can   be   improved   by  prototyping,   parts-treeing,
resolution-limiting and procedural-generating;  without a good  basic
geometric model the general techniques amplify the background noise.
{|;λ10;JA}
BOX 1.2	{JC} DESIRABLE PROPERTIES FOR A GEOMETRIC MODEL.
{↓}
	1. Spatial addressing.
	2. Spatial uniqueness.
	3. Object coherence.
	4. Surface coherence.
	5. Shape generality.
{↑;w500;}
	6. Large extent with high resolution.
	7. Readily modifiable.
	8. Suitable for simulation.
	9. Feasible memory and computation requirements.
       10. Potential for automatic model acquistion.
{|;λ30;JU}
	To the best of  my knowledge, this survey is  complete. As of
this year, 1974,  there are no other significantly different kinds of
simple geometric models. The desirable properties that have turned up
in this survey are listed in box 1.2. The final desirable property is
that  there be some  hope that the  computer can derive  the model by
measurements it can make itself, although it is quite likely that one
model  will be  best for  input and  another model  will be  best for
simulation.{Q}
⊂1.2	Polyhedron Definitions and Properties.⊃

	In  computational  modeling,     definitions  are   not  used
formally,   but are rather  employed piecemeal in  terms of individual
properties which may or may not be present as polyhedra are generated
and processed. In particular, the properties listed in box 1.3 (given
in  order of  relevance) can be  taken as  a working  definition of a
polyhedron for modeling a physical object.
{|;λ10;JA}
BOX 1.3	{JC} PROPERTIES OF POLYHEDRA.
{JA,FA↓}
	1. Eulerian.
	2. Surface Homogeneity.
	3. Trivalence.
	4. Face Planarity.
	5. Solidity.
	6. Simply Connected Faces.
	7. Face Convexity.
	8. Edge Aplanarity.
{↑;W600;}
Satisfies the Euler equation:  F-E+V=2-2*H.
The polyhedron does not intersect itself.
All vertices and faces have three or more edges.
All the vertices of a face are coplanar.
The volume measure is non-zero, finite and positive.
Face perimeters have one loop of edges.
All the faces are convex.
Faces which share an edge are not coplanar.
{|;λ30;JU}
	Topologically, the  surface elements of  a polyhedron  form a
graph that satisfies Euler's F-E+V=2-2*H equation; where as before F,
E and  V  are  the number  of  faces,    edges and  vertices  of  the
polyhedron; and where H  is the number of holes in  (or genus of) the
polyhedron.   However,  not all Eulerian  graphs of faces,  edges and
vertices correspond to the usual notion of a  solid polyhedra without
the  surface  homogeneity   and  trivalence  restrictions.    Surface
homogeneity is the property  that for any point  on the polyhedron  a
small enough sphere will  cut from the surface a  region homeomorphic
to  a  disk;  this  restriction  implies  that  the surface  can  not
intersect itself  and  that edges  can  only  belong to  exactly  two
different faces.   The trivalence restriction insures  that their are
no  degenerate two edged faces or one  edged vertices; although a two
edged  vertex has  a  reasonible  interpretation it  is  excluded  by
trivalence for  the sake of  face-vertex duality and  canonical form.
The last property, of aplanarity of faces with a common edge, is also
for the sake  of canonical form  and is sacrificed to  face convexity
when necessary.

	Geometrically, the faces of a polyhedron  are planar, that is
lie in a  plane. It is also frequently relevant to further restricted
the faces of a polyhedron to  be convex, that is every possible  line
segment between  points of a  face is  contained within the  face. To
assure  solidity, the volume measure must  be restricted to be finite
and  positive;  this restriction  orients  the  surface  to  have  an
exterior and  an interior in the expected  fashion.  This restriction
excludes non-orientable  structures such  as Mobius  bands and  Klein
bottles  for which  the  volume  measure  is undefined;  however  the
restriction  will be  slightly relaxed  in chapter  five in  order to
exploit the concept of negative volumes.

	The  working   definition  was   derived  from  more   formal
definitions  such  the  following which  defines  a  polyhedron as  a
special kind of a two dimensional manifold:
{λ7;W100,1160;}
\"A polyhedron is a connected, unbounded two-dimensional
manifold formed by a finite set of non-re-entrant, simply-connected
plane polygons."
{λ30;JR} - Coxeter, Regular Polytopes [Coxeter 1963].
{W0,1260;I∂20,0;
}\A <connected>  manifold is an  entity that is  not disjoint  and an
<unbounded> manifold is one with no cuts or gaps in its surface, that
is no  boundaries.   A  polyhedral manifold  is composed  of  planar,
simply-connected, non-re-entrant polygons; that is flat polygons with
a  perimeter  of edges  that  form  one loop  that  doesn't intersect
itself.  The polyhedron  restrictions  and  properties  are  directed
towards modeling physical objects and are maintained by computational
mechanisms; consequently the word <polyhedron> comes to represent  an
intent,   rather  than  the  fulfillment  of any  particular  set  of
defining properties. {Q}
⊂1.3	Camera, Light and Image Modeling.⊃

	Common to both computer graphics and  vision is the necessity
to  model  cameras,    light  and  images  so  that pictures  may  be
synthesized or  analysized.
The basic camera model has eight degrees of freedom, three
in location, three in orientation and two in projection:{λ10;
JA}		Location:	CX, CY, CZ		Vector to camera lens center.
		Orientation:	WX, WY, WZ		Orientation vector.
		Projection:	AR, FR		Aspect Ratio and Focal Ratio.{λ30;JU}
\The orientation vector is explained in  section 3.3, the perspective
projection is defined in section 3.4, the automatic derivation of the
camera parameters  is the  main topic  of chapter  nine. In  modeling
light and physical objects, the most important and difficult property
to  simulate is opacity.  Techniques for modeling  opaque objects are
presented in chapter four.

	Finally,  an image is a 2-D geometric object representing the
content of a rectangle from the pattern of light of light formed by a
thin lens on a television  vidicon. The video image is the  interface
to the external reality. Image modeling is analogous to 3-D geometric
modeling,   since  the same  tradeoffs between spatial  structure and
object structure arise.   A 2-D image  may be represented as  a video
raster, which is a 2-D space  array or as a set of feature loci which
is an object oriented description.   Image structures and  processors
for generating and  comparing image representations are  discussed in
chapters seven and eight.  Together camera,  light and image modeling
are the essential  elements required  to apply a  geometric model  to
computer vision. {Q}
⊂1.4	Related Modeling Work.⊃

	Although geometric modeling per  se has a long history  and a
rich literature  in mathematics, physics and engineering; very little
such modeling has been done using  a computer at the level of  detail
required  for visual  perception,   a level  which falls  between the
generality  typical in physics and  mathematics and the specificality
typical of engineering.  Computer science research  work in geometric
modeling  has already been  cited in  section 1.2; similar  ideas are
available from computer graphics sources [Newman and Sproull].  In
computer graphics, the typical modeling paper invariably has a lot of
discussion  about  the  theory  and  implementation  of  a  node/link
modeling language (CORAL,   LEAP, ASP,   and others) and very  little
material about how the actual geometric modeling is to be done in the
given  language.   In  mathematics,   I have  found  the work  of the
Canadian geometer Coxeter,[Coxeter 61] and [Coxeter 63] to be my best
source  of ideas relevant  to modeling;  along with  the observations
from recreational  mathematicians [Gardner  59],   [Gardner  61]  and
[Stewart];  and  geometry  textbook authors  [Eves],    [Snyder]  and
[Graustein].   The translation of Hilbert's book [Hilbert] presenting
Geometry for the  non-mathematician is also a  good source of  ideas.
With  the  exception  of   general  relativistic  gravitation  theory
[Misner,    Thorne and  Wheeler]  geometric  modeling is  not  at the
frontier physics research; although classical mechanics is applicable
to some  aspects of rotation  and tensors [Goldstein],  [Feynman] and
[Symon]. In engineering,   books on  geodetic surveying,   mechanical
drawing and architectural drawing contain  ideas relevant to modeling
particular  classes of objects;  selected almost  at random,   I have
used [Luzadder]  and  [Muller] as  introductions to  engineering  and
architectural drawing respectively.